package lcr;

public class Test0029 {
    public static void main(String[] args) {
        Node node1 = new Node(3);
        Node node2 = new Node(5);
        Node node3 = new Node(1);

        node1.next = node2;
        node2.next = node3;

        new Solution0029_1().insert(null,0);
    }
}
class Solution0029_1 {
    public Node insert(Node head, int insertVal) {
        Node node = new Node();
        node.val=insertVal;
        if (head==null){
            node.next=node;
            return node;
        }

        Node ans=head;
        while (head.next!=null){
            int nVal = head.next.val;
            int hVal = head.val;
            if ((hVal <=insertVal&& nVal >=insertVal)
                    ||(nVal < hVal &&(insertVal>= hVal||insertVal<=nVal))||head.next==ans){
                node.next=head.next;
                head.next=node;
                break;
            }
            head=head.next;
        }

        return ans;
    }

}